package awesomeness.handin1;
import java.util.ArrayList;


public class GiantBook {

	private WeightedQuickUnionUF qu;
	private boolean giantFound, nonisolatedFound;
	private int tries, connectedTotal, nonisolatedTotal, giantTotal;
	private int[] connected, nonisolated, giant;
	private ArrayList<Integer> connectedList, nonisolatedList, giantList;

	public static void main(String[] args) {
		new GiantBook(100, 100);
	}

	public GiantBook(int N, int T) {

		connectedList = new ArrayList<Integer>();
		giantList = new ArrayList<Integer>();
		nonisolatedList = new ArrayList<Integer>();

		for (int i = 0; i < T; i++) {
			tries = 0;
			giantFound = false;
			nonisolatedFound = false;

			qu = new WeightedQuickUnionUF(N);

			while (qu.count() != 1) {
				qu.union(StdRandom.uniform(N), StdRandom.uniform(N));

				if (!giantFound) checkGiantNetwork(N);
				if (!nonisolatedFound) checkNonIsolatedNetwork(); 

				tries++;
			}

			connectedTotal += tries;
			connectedList.add(tries);
		}

		connected = new int[connectedList.size()];
		for (int i = 0; i < connectedList.size(); i++) {
			connected[i] = connectedList.get(i);
		}		
		nonisolated = new int[nonisolatedList.size()];
		for (int i = 0; i < nonisolatedList.size(); i++) {
			nonisolated[i] = nonisolatedList.get(i);
		}		
		giant = new int[giantList.size()];
		for (int i = 0; i < giantList.size(); i++) {
			giant[i] = giantList.get(i);
		}

		StdOut.print("Connected: ");
		StdOut.print(String.valueOf((connectedTotal / T)));
		StdOut.print(" (" + StdStats.stddev(connected) + ")\n");

		StdOut.print("Giant: ");
		StdOut.print(String.valueOf((giantTotal / T)));
		StdOut.print(" (" + StdStats.stddev(giant) + ")\n");

		StdOut.print("Non-isolated: ");
		StdOut.print(String.valueOf((nonisolatedTotal / T)));
		StdOut.print(" (" + StdStats.stddev(nonisolated) + ")");

	}

	public void checkGiantNetwork(int N) {
		if (qu.hasGiant()) {
			giantTotal += tries;
			giantList.add(tries);
			giantFound = true;
		}
	}

	public void checkNonIsolatedNetwork() {
		if (qu.singles() == 0) {
			nonisolatedTotal += tries;
			nonisolatedList.add(tries);
			nonisolatedFound = true;
		}
	}
}
